{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Convert Sorted List to Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #linked-list #divide-and-conquer #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #链表 #分治 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortedListToBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有序链表转换二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个单链表的头节点 &nbsp;<code>head</code>&nbsp;，其中的元素 <strong>按升序排序</strong> ，将其转换为高度平衡的二叉搜索树。</p>\n",
    "\n",
    "<p>本题中，一个高度平衡二叉树是指一个二叉树<em>每个节点&nbsp;</em>的左右两个子树的高度差不超过 1。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2020/08/17/linked.jpg\" style=\"height: 388px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [-10,-3,0,5,9]\n",
    "<strong>输出:</strong> [0,-3,9,-10,null,5]\n",
    "<strong>解释:</strong> 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = []\n",
    "<strong>输出:</strong> []\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>head</code>&nbsp;中的节点数在<code>[0, 2 * 10<sup>4</sup>]</code>&nbsp;范围内</li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [convert-sorted-list-to-binary-search-tree](https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [convert-sorted-list-to-binary-search-tree](https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-10,-3,0,5,9]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, nums, i, j):\n",
    "        if i > j:\n",
    "            return None\n",
    "        \n",
    "        m = (i + j) // 2\n",
    "        \n",
    "        node = TreeNode(nums[m])\n",
    "        node.left = self.buildTree(nums, i, m - 1)\n",
    "        node.right = self.buildTree(nums, m + 1, j)\n",
    "        return node\n",
    "        \n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        \n",
    "        node = head\n",
    "        nums = []\n",
    "        while node:\n",
    "            nums.append(node.val)\n",
    "            node = node.next\n",
    "        \n",
    "        return self.buildTree(nums, 0, len(nums) - 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return \n",
    "        \n",
    "        if not head.next:\n",
    "            return TreeNode(head.val)\n",
    "        \n",
    "        slow, fast = head, head.next.next\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next \n",
    "            fast = fast.next.next\n",
    "            \n",
    "        tmp = slow.next\n",
    "        slow.next = None\n",
    "        res = TreeNode(tmp.val)\n",
    "        res.left = self.sortedListToBST(head)\n",
    "        res.right = self.sortedListToBST(tmp.next)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return None\n",
    "        if  not head.next:\n",
    "            return TreeNode(head.val)\n",
    "        tmp = head\n",
    "        length = 0\n",
    "        while head.next:\n",
    "            length+=1\n",
    "            head = head.next\n",
    "        head = tmp\n",
    "        for i in range(int(length/2)-1):\n",
    "            tmp = tmp.next\n",
    "        root = TreeNode(tmp.next.val)\n",
    "        righthead = tmp.next.next\n",
    "        tmp.next = None\n",
    "        lefthead = head\n",
    "        root.right = self.sortedListToBST(righthead)\n",
    "        root.left = self.sortedListToBST(lefthead)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        # base case\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return TreeNode(head.val)\n",
    "        # find subtree root node, which is the middle element , using slow fast pointer method\n",
    "        slow = fast =  head\n",
    "        prev = None\n",
    "        while fast and fast.next:\n",
    "            prev = slow\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        root = TreeNode(slow.val)      # slow is the root node\n",
    "        prev.next = None             # prev is the node before root, set prev.next to None to cut off the 1st half linked list\n",
    "        root.left  = self.sortedListToBST(head)              # recursion on 1st half of list and set to left child\n",
    "        root.right = self.sortedListToBST(slow.next)         # recursion on 2nd half of list and set to right child\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # @param head, a list node\n",
    "    # @return a tree node\n",
    "    def convert(self,head,tail):\n",
    "        if head==tail:\n",
    "            return None\n",
    "        if head.next==tail:\n",
    "            return TreeNode(head.val)\n",
    "        mid=head\n",
    "        fast=head\n",
    "        while fast!=tail and fast.next!=tail:\n",
    "            fast=fast.next.next\n",
    "            mid=mid.next\n",
    "        node=TreeNode(mid.val)\n",
    "        node.left=self.convert(head,mid)\n",
    "        node.right=self.convert(mid.next,tail)\n",
    "        return node\n",
    "    def sortedListToBST(self, head):\n",
    "        return self.convert(head,None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.helper(self.helperlist(head))\n",
    "    \n",
    "    def helperlist(self,head):\n",
    "        res=[]\n",
    "        \n",
    "        while head:\n",
    "            res.append(head.val)\n",
    "            head=head.next\n",
    "            \n",
    "        return res\n",
    "    \n",
    "    def helper(self,nums):\n",
    "        if not nums:\n",
    "            return None\n",
    "        \n",
    "        pos=int(len(nums)/2)\n",
    "        \n",
    "        root=TreeNode(nums[pos])\n",
    "        \n",
    "        root.left=self.helper(nums[:pos])\n",
    "        root.right=self.helper(nums[pos+1:])\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        newlist=[]\n",
    "        while head:\n",
    "            newlist.append(head.val)\n",
    "            head=head.next\n",
    "        return self.buildTree(newlist)\n",
    "    \n",
    "    def buildTree(self, newlist):\n",
    "        if not newlist:\n",
    "            return None\n",
    "        mid=int(len(newlist)/2)\n",
    "        print(newlist[mid])\n",
    "        root=TreeNode(newlist[mid])\n",
    "        root.left=self.buildTree(newlist[:mid])\n",
    "        root.right=self.buildTree(newlist[mid+1:])\n",
    "        return root\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return None\n",
    "        nums = []\n",
    "        node = head\n",
    "        while node:\n",
    "            nums.append(node.val)\n",
    "            node = node.next\n",
    "        return self.sortedToBST(nums)    \n",
    "            \n",
    "            \n",
    "            \n",
    "    def sortedToBST(self, nums):\n",
    "        if not nums:\n",
    "            return None\n",
    "        mid = (len(nums) - 1) //2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedToBST(nums[:mid])\n",
    "        root.right = self.sortedToBST(nums[mid+1:])\n",
    "        return root\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findmid(self, head):\n",
    "        prePtr = None\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast and fast.next:\n",
    "            prePtr = slow\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        \n",
    "        if prePtr:\n",
    "            prePtr.next = None\n",
    "        return slow\n",
    "    \n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        mid = self.findmid(head)\n",
    "\n",
    "        node = TreeNode(mid.val)\n",
    "        if head == mid:\n",
    "            return node\n",
    "\n",
    "        node.left = self.sortedListToBST(head)\n",
    "        node.right = self.sortedListToBST(mid.next)\n",
    "\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        if not head: return None\n",
    "        if not head.next: return TreeNode(head.val)\n",
    "\n",
    "        def find_mid(head):\n",
    "            slow = fast = head\n",
    "            prev = None\n",
    "            \n",
    "            while fast and fast.next:\n",
    "                prev = slow\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            if prev: prev.next = None\n",
    "            return slow\n",
    "\n",
    "        mid = find_mid(head)\n",
    "        root = TreeNode(mid.val)\n",
    "        root.left = self.sortedListToBST(head)\n",
    "        root.right = self.sortedListToBST(mid.next)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "class ListNode:\r\n",
    "    def __init__(self, x):\r\n",
    "        self.val = x\r\n",
    "        self.next = None\r\n",
    "\r\n",
    "# Definition for a binary tree node.\r\n",
    "class TreeNode:\r\n",
    "    def __init__(self, x):\r\n",
    "        self.val = x\r\n",
    "        self.left = None\r\n",
    "        self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\r\n",
    "\r\n",
    "        def find_mid_node(head):\r\n",
    "            prev = None\r\n",
    "            slow_node = head\r\n",
    "            fast_node = head\r\n",
    "            \r\n",
    "            while fast_node and fast_node.next:\r\n",
    "                prev = slow_node\r\n",
    "                slow_node = slow_node.next\r\n",
    "                fast_node = fast_node.next.next\r\n",
    "            \r\n",
    "            # 通过此方式，断开左边的列表\r\n",
    "            if prev:\r\n",
    "                prev.next = None\r\n",
    "            \r\n",
    "            return slow_node\r\n",
    "\r\n",
    "        def sortedlist_to_bst(head):\r\n",
    "            if not head: return None\r\n",
    "\r\n",
    "            mid = find_mid_node(head)\r\n",
    "            root = TreeNode(mid.val)\r\n",
    "            \r\n",
    "            if head == mid: return root\r\n",
    "            \r\n",
    "            root.left = sortedlist_to_bst(head)\r\n",
    "            root.right = sortedlist_to_bst(mid.next)\r\n",
    "            return root\r\n",
    "        \r\n",
    "        return sortedlist_to_bst(head)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        def findmid(head):\n",
    "            first,second=head,head\n",
    "            pre=None\n",
    "            while second and second.next:\n",
    "                pre=first\n",
    "                first=first.next\n",
    "                second=second.next.next\n",
    "            if pre: pre.next=None\n",
    "            return first\n",
    "        \n",
    "        def list2BST(head):\n",
    "            if not head:\n",
    "                return None\n",
    "            mid=findmid(head)\n",
    "            curr=TreeNode(mid.val)\n",
    "            if mid==head :\n",
    "                return curr\n",
    "            \n",
    "            curr.left=list2BST(head)\n",
    "            curr.right=list2BST(mid.next)\n",
    "            return curr\n",
    "        \n",
    "        return list2BST(head)\n",
    "            \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        pre, slow, fast = None, head, head\n",
    "\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "        if pre:\n",
    "            pre.next = None\n",
    "        node = TreeNode(slow.val)\n",
    "        if slow == fast:\n",
    "            return node\n",
    "        node.left = self.sortedListToBST(head)\n",
    "        node.right = self.sortedListToBST(slow.next)\n",
    "        return node\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "        if head.next is None:\n",
    "            return TreeNode(head.val)\n",
    "        pre, slow, fast = None, head, head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "        root = TreeNode(slow.val)\n",
    "        if pre:\n",
    "            pre.next = None\n",
    "        root.left = self.sortedListToBST(head)\n",
    "        root.right = self.sortedListToBST(slow.next)\n",
    "        return root\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        pre, slow, fast = None, head, head\n",
    "\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "        if pre:\n",
    "            pre.next = None\n",
    "        node = TreeNode(slow.val)\n",
    "        if slow == fast:\n",
    "            return node\n",
    "        node.left = self.sortedListToBST(head)\n",
    "        node.right = self.sortedListToBST(slow.next)\n",
    "        return node\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# fast and slow pointers\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return TreeNode(head.val)\n",
    "        pre = head\n",
    "        p = pre.next\n",
    "        q = p.next\n",
    "        # find midpoint = p\n",
    "        while q and q.next:\n",
    "            pre = pre.next\n",
    "            p = pre.next\n",
    "            q = q.next.next\n",
    "        pre.next = None\n",
    "        return TreeNode(val=p.val, left=self.sortedListToBST(head), right=self.sortedListToBST(p.next))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        #[-10,-3,0,5,9]\n",
    "        if not head: return None\n",
    "        if not head.next: return TreeNode(head.val)\n",
    "        \n",
    "        slow, fast = head, head\n",
    "        \n",
    "        while fast and fast.next:\n",
    "            slow, fast = slow.next, fast.next.next\n",
    "            \n",
    "        pre = head\n",
    "        while pre.next != slow:\n",
    "            pre = pre.next\n",
    "        pre.next = None\n",
    "            \n",
    "        root = TreeNode(slow.val)\n",
    "        root.left = self.sortedListToBST(head)\n",
    "        root.right = self.sortedListToBST(slow.next)\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        if not head: return None\n",
    "        if not head.next: return TreeNode(head.val)\n",
    "        fast = head\n",
    "        slow = head\n",
    "        pre = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "        pre.next = None\n",
    "        root = TreeNode(slow.val)\n",
    "        root.left = self.sortedListToBST(head)\n",
    "        root.right = self.sortedListToBST(slow.next)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        p1, p2, p3 = head, head.next, None\n",
    "        while p2 and p2.next:\n",
    "            p3 = p1\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next.next\n",
    "        if p3:\n",
    "            p3.next = None\n",
    "        else:\n",
    "            head = None\n",
    "        root = TreeNode(p1.val)\n",
    "        root.left  = self.sortedListToBST(head)\n",
    "        root.right = self.sortedListToBST(p1.next)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        def getMid(head):\n",
    "            slow,fast=head,head.next\n",
    "            while fast.next and fast.next.next:\n",
    "                fast=fast.next.next\n",
    "                slow=slow.next\n",
    "            return slow\n",
    "\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            if not root.next:\n",
    "                return TreeNode(root.val)\n",
    "\n",
    "            mid=getMid(root)\n",
    "            tmp=mid.next\n",
    "\n",
    "            mid.next=None\n",
    "            \n",
    "            ret=TreeNode(tmp.val)\n",
    "            \n",
    "            ret.right=helper(tmp.next)\n",
    "            ret.left=helper(root)\n",
    "            return ret\n",
    "        return helper(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "        pre , slow ,fast=None,head,head\n",
    "        while fast and fast.next:\n",
    "            fast=fast.next.next\n",
    "            pre=slow\n",
    "            slow=slow.next\n",
    "        if pre:\n",
    "            pre.next=None\n",
    "        node=TreeNode(slow.val)\n",
    "        if slow==fast:\n",
    "            return node\n",
    "        node.left=self.sortedListToBST(head)\n",
    "        node.right=self.sortedListToBST(slow.next)\n",
    "        return node\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# # Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class ListNode:\n",
    "#     def __init__(self, val):\n",
    "#         self.val =val\n",
    "#         self.next = None\n",
    "\n",
    "class Solution(object):\n",
    "    def sortedListToBST(self, head):\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return TreeNode(head.val)\n",
    "        pre=None\n",
    "        slow=fast=head\n",
    "        while fast and fast.next:\n",
    "            pre=slow\n",
    "            slow=slow.next\n",
    "            fast=fast.next.next\n",
    "        pre.next=None\n",
    "        root=TreeNode(slow.val)\n",
    "        root.left=self.sortedListToBST(head)\n",
    "        root.right=self.sortedListToBST(slow.next)\n",
    "        return root            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeToBST(self, left: int, right: int) -> TreeNode:\n",
    "        if right < left:\n",
    "            return None\n",
    "\n",
    "        mid = (left + right) // 2\n",
    "        left_node = self.mergeToBST(left, mid - 1)\n",
    "\n",
    "        root = TreeNode(self.head.val)\n",
    "\n",
    "        self.head = self.head.next\n",
    "        right_node = self.mergeToBST(mid + 1, right)\n",
    "\n",
    "        root.left = left_node\n",
    "        root.right = right_node\n",
    "        return root\n",
    "\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        self.head = head\n",
    "        p = head\n",
    "        link_list_len = 0\n",
    "        while p:\n",
    "            p = p.next\n",
    "            link_list_len += 1\n",
    "        return self.mergeToBST(0, link_list_len - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        if head is None:\n",
    "            return\n",
    "        fast, slow = head, head\n",
    "        pre = None\n",
    "        while fast.next and fast.next.next:\n",
    "            fast = fast.next.next\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "        root = TreeNode(slow.val)\n",
    "        if pre:\n",
    "            pre.next = None \n",
    "            root.left = self.sortedListToBST(head)\n",
    "        root.right = self.sortedListToBST(slow.next)\n",
    "        print(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return TreeNode(head.val)\n",
    "        pre, mid , end = head, head, head\n",
    "        while end and end.next:\n",
    "            end = end.next.next\n",
    "            pre = mid\n",
    "            mid = mid.next\n",
    "        pre.next = None\n",
    "        root = TreeNode(mid.val)\n",
    "        right = mid.next\n",
    "        mid.next = None\n",
    "        root.left = self.sortedListToBST(head)\n",
    "        root.right = self.sortedListToBST(right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        prev = head\n",
    "        p1 = head\n",
    "        p2 = head\n",
    "        while p2 and p2.next:\n",
    "            prev = p1\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next.next\n",
    "\n",
    "        if p1 == p2:\n",
    "            if p1 is None:\n",
    "                return \n",
    "            root = TreeNode(p1.val)\n",
    "            return root\n",
    "\n",
    "        root = TreeNode(p1.val)\n",
    "        prev.next = None\n",
    "        root.left = self.sortedListToBST(head)\n",
    "        root.right = self.sortedListToBST(p1.next)\n",
    "        return root\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def len(self,head):\r\n",
    "        cur = ListNode(next=head)\r\n",
    "        L = 0\r\n",
    "        while cur.next:\r\n",
    "            L+=1\r\n",
    "            cur = cur.next\r\n",
    "        return L\r\n",
    "    \r\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\r\n",
    "        L = self.len(head)\r\n",
    "        print(L)\r\n",
    "        cur = ListNode(next=head)\r\n",
    "        if L==0:\r\n",
    "            return None\r\n",
    "        if L==1:\r\n",
    "            return TreeNode(val=head.val)\r\n",
    "        for i in range(L//2):\r\n",
    "            cur = cur.next\r\n",
    "        pre = cur\r\n",
    "        cur = cur.next\r\n",
    "        pos = cur.next\r\n",
    "        pre.next=None\r\n",
    "        root = TreeNode(val=cur.val)\r\n",
    "        root.left = self.sortedListToBST(head)\r\n",
    "        root.right = self.sortedListToBST(pos)\r\n",
    "        return root\r\n",
    "\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        res = []\n",
    "        while head:\n",
    "            res.append(head.val)\n",
    "            head = head.next\n",
    "        def dfs(res, left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "            mid = (right - left) // 2 + left\n",
    "            root = TreeNode(res[mid])\n",
    "            root.left = dfs(res, left, mid-1)\n",
    "            root.right = dfs(res, mid + 1, right)\n",
    "            return root\n",
    "\n",
    "        return dfs(res, 0, len(res)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        def getLength(head: ListNode) -> int:\n",
    "            ret = 0\n",
    "            while head:\n",
    "                ret += 1\n",
    "                head = head.next\n",
    "            return ret\n",
    "        \n",
    "        def buildTree(left: int, right: int) -> TreeNode:\n",
    "            if left > right:\n",
    "                return None\n",
    "            mid = (left + right + 1) // 2\n",
    "            root = TreeNode()\n",
    "            root.left = buildTree(left, mid - 1)\n",
    "            nonlocal head\n",
    "            root.val = head.val\n",
    "            head = head.next\n",
    "            root.right = buildTree(mid + 1, right)\n",
    "            return root\n",
    "        \n",
    "        length = getLength(head)\n",
    "        return buildTree(0, length - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        p = head\n",
    "        count = 0\n",
    "        while p:\n",
    "            count += 1\n",
    "            p = p.next\n",
    "        self.cur = head\n",
    "        res = self.construct(0, count-1)\n",
    "        return res\n",
    "\n",
    "    def construct(self, start: int, end: int) -> TreeNode:\n",
    "        if start > end:\n",
    "            return None\n",
    "        #print(self.cur, start, end)\n",
    "        root = TreeNode()\n",
    "        mid = (start + end) // 2\n",
    "        left = self.construct(start, mid - 1)\n",
    "        root.val = self.cur.val\n",
    "        root.left = left\n",
    "        self.cur = self.cur.next\n",
    "        right = self.construct(mid + 1, end)\n",
    "        root.right = right\n",
    "        #print(root, self.cur)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        #分治+DFS 注意顺序 buildTree中head需要随着递归变化，全局变量声明\n",
    "        def getlength(head):\n",
    "            res = 0\n",
    "            while head:\n",
    "                res += 1\n",
    "                head = head.next\n",
    "            return res\n",
    "        \n",
    "        def buildTree(left,right):\n",
    "            \"\"\"\n",
    "            type: int\n",
    "            \"\"\"\n",
    "            if left >right:\n",
    "                return None\n",
    "            mid = (left+right+1)//2\n",
    "            root = TreeNode()\n",
    "            root.left = buildTree(left,mid-1)\n",
    "            nonlocal head\n",
    "            root.val = head.val\n",
    "            head = head.next\n",
    "            root.right = buildTree(mid+1,right)\n",
    "            return root\n",
    "        return buildTree(0,getlength(head)-1)  \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        nums = []\n",
    "        while head is not None:\n",
    "            nums.append(head.val)\n",
    "            head = head.next\n",
    "        def build_tree(left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "            mid = (left + right) // 2\n",
    "            val = nums[mid]\n",
    "            node = TreeNode(val)\n",
    "            node.left = build_tree(left, mid - 1)\n",
    "            node.right = build_tree(mid + 1, right)\n",
    "            return node\n",
    "        return build_tree(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        n = 0\n",
    "        node = head\n",
    "        while node:\n",
    "\n",
    "            n += 1\n",
    "            node = node.next\n",
    "        \n",
    "        def build(node, length):\n",
    "\n",
    "            #print(f'{node} {length}')\n",
    "\n",
    "            if length == 0:\n",
    "                return None\n",
    "\n",
    "            mid = length // 2\n",
    "            l_length = mid\n",
    "            r_length = length - mid - 1\n",
    "\n",
    "            mid_node = node\n",
    "            pre_mid = None\n",
    "\n",
    "            while mid > 0:\n",
    "                mid -= 1\n",
    "                pre_mid = mid_node\n",
    "                mid_node = mid_node.next\n",
    "\n",
    "            \n",
    "\n",
    "            cur_tree_node = TreeNode(mid_node.val)\n",
    "\n",
    "            cur_tree_node.left = build(node, l_length)\n",
    "            cur_tree_node.right = build(mid_node.next, r_length)\n",
    "        \n",
    "            return cur_tree_node\n",
    "        \n",
    "        return build(head, n)\n",
    "        \n",
    "        # from ans, use in order tranverse and after build left tree the cur list node is cur tree node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        def getMedian(left: ListNode, right: ListNode) -> ListNode:\n",
    "            fast = slow = left\n",
    "            while fast != right and fast.next != right:\n",
    "                fast = fast.next.next\n",
    "                slow = slow.next\n",
    "            return slow\n",
    "        \n",
    "        def buildTree(left: ListNode, right: ListNode) -> TreeNode:\n",
    "            if left == right:\n",
    "                return None\n",
    "            mid = getMedian(left, right)\n",
    "            root = TreeNode(mid.val)\n",
    "            root.left = buildTree(left, mid)\n",
    "            root.right = buildTree(mid.next, right)\n",
    "            return root\n",
    "        \n",
    "        return buildTree(head, None)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        n = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            n += 1\n",
    "        \n",
    "        def helper(head, l, r):\n",
    "            if l > r:\n",
    "                return None\n",
    "            mid = (r-l) // 2 + l\n",
    "            t = mid - l\n",
    "            cur = head\n",
    "            while t > 0:\n",
    "                cur = cur.next\n",
    "                t -= 1\n",
    "            \n",
    "            ans = TreeNode(cur.val)\n",
    "            ans.left = helper(head, l, mid-1)\n",
    "            ans.right = helper(cur.next, mid+1, r)\n",
    "\n",
    "            return ans\n",
    "        \n",
    "        return helper(head, 0, n-1)\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
